//
// https://leetcode-cn.com/problems/maximum-swap/solution/zui-da-jiao-huan-onlogn-by-wangyunpan/
// 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
// 输入: 2736
// 输出: 7236
// 解释: 交换数字2和数字7
//

class Solution
{
public:
  int maximumSwap(int num)
  {
    // 小于10，不用交换，直接返回
    if (num <= 10)
      return num;

    // num => string
    string s = to_string(num);

    // 不断的两两字符交换，判断交换后的数，是否比 num 大
    for (int i = 0; i < s.size(); i++) // i: 0 -> N
      for (int j = i + 1; j < s.size(); j++) // j: 1+1 -> N
      {
        // 1. 交换
        swap(s[i], s[j]);

        // 2. string => num
        int t = atoi(s.c_str());

        // 3. 保存交换后的【最大】数值
        if (t > num)
          num = t;

        // 4. 恢复交换
        swap(s[i], s[j]);
      }

    return num;
  }
};